package org.example.leetcode.interview.greed;

public class LC0134 {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int currGas = 0;
        int totalGas = 0;
        int index = 0;

        for (int i = 0; i < gas.length; i++) {
            currGas += gas[i] - cost[i];
            totalGas += gas[i] - cost[i];
            if (currGas < 0) {
                index = (i + 1) % gas.length;
                currGas = 0;
            }
        }
        if (totalGas < 0) return -1;

        return index;
    }
}
